package com.clei.algorithm.other;

import com.clei.utils.PrintUtil;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

/**
 * 贪心算法
 * 钱币找零
 *
 * @author Y
 * @date 2022-12-16
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {
        // 当前有零钱 j0表示面额 j1表示数目 {100,6}表示有6张面额100的纸币
        int[][] change = {{100, 6}, {50, 7}, {20, 8}, {10, 9}, {5, 10}, {1, 11}};
        // 需要找零的金额
        int need = 878;
        // 忽略找不够和小数的问题
        int[][] returnChange = getChange(change, need);
        PrintUtil.log("找零：{}",
                Arrays.stream(returnChange)
                        .filter(a -> a[1] > 0)
                        .map(a -> String.format("%d元%d张", a[0], a[1]))
                        .collect(Collectors.joining(",")));

        PrintUtil.log("剩余零钱：{}",
                Arrays.stream(change)
                        .filter(a -> a[1] > 0)
                        .map(a -> String.format("%d元%d张", a[0], a[1]))
                        .collect(Collectors.joining(",")));
    }

    /**
     * 找零
     * 需要给的钱的张数尽可能的少
     * 尽量给面额大的
     *
     * @param change 当前的零钱
     * @param need   需要找零金额
     * @return 零钱
     */
    private static int[][] getChange(int[][] change, int need) {
        int[][] res = {{100, 0}, {50, 0}, {20, 0}, {10, 0}, {5, 0}, {1, 0}};
        // 已有零钱先做由高到低的排序
        change = Arrays.stream(change).sorted(Comparator.comparingInt(a -> -a[0])).toArray(int[][]::new);
        for (int i = 0; i < change.length; i++) {
            int[] paperMoney = change[i];
            // 纸币数判断 要有当前面额的纸币且当前需要找零金额大于其面额值
            if (paperMoney[1] > 0) {
                int paperCount = need / paperMoney[0];
                if (paperCount > 0) {
                    paperCount = Math.min(paperCount, paperMoney[1]);
                    need -= paperCount * paperMoney[0];
                    paperMoney[1] -= paperCount;
                    res[i][1] += paperCount;
                    if (0 == need) {
                        break;
                    }
                }
            }
        }
        if (0 != need) {
            PrintUtil.log("找不够啊");
        }
        return res;
    }
}
